package com.lhcai.lc.category.prefixsum;

import java.util.Arrays;

/**
 * 2090. 半径为 k 的子数组平均值
 *
 * @author liuhuaicai
 * @since 2024-10-20 15:44
 */
public class Lc2090 {
    public static void main(String[] args) {
        Lc2090 lc2090 = new Lc2090();
        System.out.println(Arrays.toString(lc2090.getAverages(new int[]{7, 4, 3, 9, 1, 8, 5, 2, 6}, 3)));
    }

    // 前缀和
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        // 获取前缀和 要用long型，不然超出范围
        long[] pre = new long[n + 1];
        for (int i = 1; i < n + 1; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        // 求 i - k 到 i + k之间的值，则为sum[i + k] - sum[i - k -1]
        // 因为pre向后了一位，则为求 pre[i + k +1 ] - pre[i - k]
        for (int i = 0; i < n; i++) {
            if (i >= k && i <= n - k - 1) {
                res[i] = (int) ((pre[i + k + 1] - pre[i - k]) / (2 * k + 1));
            }
        }
        return res;
    }

    // 暴力循环 超出时间限制
    // 39 / 40 个通过的测试用例
//    public int[] getAverages(int[] nums, int k) {
//        int n = nums.length;
//        int[] avgs = new int[n];
//        for (int i = 0; i < n; i++) {
//            if (i < k || i > n - k - 1) {
//                avgs[i] = -1;
//                continue;
//            }
//            // 暴力解法，注意用long,不然会超限
//            long sum = 0;
//            for (int j = i - k; j <= i + k; j++) {
//                sum += nums[j];
//            }
//            // 商
//            long quotient = sum / (2 * k + 1);
//            avgs[i] = (int) quotient;
//        }
//        return avgs;
//    }
}
